from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


def insert(root, val):
    '''二叉搜索树插入操作'''
    if root == None:
        root = TreeNode(val)
    elif val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    return root


def print_all(node):
    if node is not None:
        print_all(node.left)
        print(node.val)
        print_all(node.right)

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not  root:
            return []
        ans=[]
        queue=[root]
        while queue:
            temp=[]
            for i in range(len(queue)):
                x=queue.pop(0)
                temp.append(x.val)
                if x.left:
                    queue.append(x.left)
                if x.right:
                    queue.append(x.right)
            ans.append(temp)
        return ans
if __name__ == '__main__':
    root = None
    nums = [1, 2, 5, 5, 5, 6, 9, 7, 8]
    for i in nums:
        root = insert(root, i)

    s=Solution()
    ans=s.levelOrder(root)
    print(ans)
